package code.classic150on2025;

public class BinSearch {
    // 74. 搜索二维矩阵
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m - 1;
        // 先二分查找找到应该在哪一行找
        int row = 0;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (matrix[mid][0] <= target) {
                row = mid;
                left = mid + 1;
            } else if (matrix[mid][0] > target) {
                right = mid - 1;
            }
        }
        // 再二分查找找到在哪一列
        left = 0;
        right = n - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (matrix[row][mid] == target)
                return true;
            else if (matrix[row][mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }

    // 162. 寻找峰值
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            // mid比两边大，得到答案
            if (findPeakCompare(mid - 1, mid, nums) < 0 && findPeakCompare(mid, mid + 1, nums) > 0) {
                return mid;
            }
            // mid比右面小，去往右面找极大值
            else if (findPeakCompare(mid, mid + 1, nums) < 0) {
                left = mid + 1;
            }
            // mid比左面小，去往左面找极大值
            else {
                right = mid - 1;
            }
        }
        return -1;
    }

    private int findPeakCompare(int a, int b, int[] nums) {
        long x = (a < 0 || a == nums.length) ? Long.MIN_VALUE : nums[a];
        long y = (b < 0 || b == nums.length) ? Long.MIN_VALUE : nums[b];
        return Long.compare(x, y);
    }

    // 33. 搜索旋转排序数组
    public int search(int[] nums, int target) {
        // nums 中的每个值都 独一无二
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target)
                return mid;
            // 如果左面没问题，且target在左面，则往左找，否则往右找；如果右面没问题，且target在右面，则往右找，否则往左找
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }

    // 34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 找最左位置
        int leftest = nums.length;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (target == nums[mid]) {
                leftest = mid;
                right = mid - 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 如果不存在，直接返回即可
        if (leftest == nums.length)
            return new int[]{-1, -1};
        // 找最右位置
        left = 0;
        right = nums.length - 1;
        int rightest = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target) {
                rightest = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{leftest, rightest};
    }

    // 153. 寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        int min = 5001;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            min = Math.min(min, nums[mid]);
            // 如果左面正常
            if (nums[left] <= nums[mid]) {
                // 哪边小去哪边
                if (nums[left] < nums[right])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 如果右面正常
            else {
                if (nums[mid - 1] < nums[mid])
                    right = mid - 1;
                else
                    return nums[mid];
            }
        }
        return min;
    }

    // 4. 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 如果是偶数个，找到中间两个数字；如果是奇数个，找到中间的那个数字
        int num = nums1.length + nums2.length;
        if (num % 2 == 0)
            return ((double) getKthNum(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, num / 2) +
                    (double) getKthNum(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, num / 2 + 1)) / 2;
        else
            return getKthNum(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, num / 2 + 1);
    }

    private int getKthNum(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        // 如果只剩一个数组，直接计算返回即可
        if (start1 > end1)
            return nums2[start2 + k - 1];
        if (start2 > end2)
            return nums1[start1 + k - 1];
        // 如果k=1了，说明已经可以找到我们要找的数字了
        if (k == 1)
            return Math.min(nums1[start1], nums2[start2]);
        // nums1、nums2分别往前找 k / 2 个数字
        int pos1 = Math.min(end1, start1 + k / 2 - 1);
        int pos2 = Math.min(end2, start2 + k / 2 - 1);
        // 🌟递归：
        if (nums1[pos1] < nums2[pos2])
            return getKthNum(nums1, pos1 + 1, end1, nums2, start2, end2, k - (pos1 - start1 + 1));
        else
            return getKthNum(nums1, start1, end1, nums2, pos2 + 1, end2, k - (pos2 - start2 + 1));
    }

    public static void main(String[] args) {
        BinSearch b = new BinSearch();
        b.findMedianSortedArrays(new int[]{2,2,4,4}, new int[]{2,2,2,4,4});
    }
}
